package Aleehot100;

import java.util.ArrayList;
import java.util.List;

/**
 * ClassName: c055
 * Package: Aleehot100
 * Description: 46 全排列
 *
 * @Author BCXJ
 * @Create 2025/8/7 08:35
 * @Version 1.0
 * @Since 1.0
 */
public class c055 {
    public static void main(String[] args) {
        int[] arr = {1,2,3};
        System.out.println(permute(arr));
    }

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        process(nums, res, 0);
        return res;
    }

    private static void process(int[] nums, List<List<Integer>> res, int path) {
        if(path == nums.length) {
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i < nums.length; i++) {
                list.add(nums[i]);
            }
            res.add(list); // 加入队列
        }

        // 递归
        for (int i = path; i < nums.length; i++) {
            swap(nums, i, path);
            process(nums, res, path + 1); // 这个递归好好悟一下
            swap(nums, i, path);
        }

    }

    // 交换元素
    private static void swap(int[] nums, int i, int path) {
        if(i == path) {
            return;
        }
        nums[i] = nums[i] ^ nums[path];
        nums[path] = nums[i] ^ nums[path];
        nums[i] = nums[i] ^ nums[path];
    }
}
